home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / src / Fix.cc < prev    next >
C/C++ Source or Header  |  1994-08-12  |  13KB  |  664 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /*
  3. Copyright (C) 1989 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18. //
  19. // Fix.cc : variable length fixed point data type class functions
  20. //
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <Fix.h>
  26. #include <std.h>
  27. #include <Obstack.h>
  28. #include <AllocRing.h>
  29. #include <strstream.h>
  30.  
  31. // member constants
  32.  
  33. const _G_uint16_t Fix::min_length;
  34. const _G_uint16_t Fix::max_length;
  35. const double Fix::min_value;
  36. const double Fix::max_value;
  37.  
  38. // default parameters
  39.  
  40. _G_uint16_t Fix::default_length = 16;
  41. int    Fix::default_print_width = 8;
  42.  
  43. Fix::PEH Fix::overflow_handler = Fix::overflow_saturate;
  44.  
  45. Fix::Rep Fix::Rep_0    = { 16, 1, 1, { 0 } };
  46. Fix::Rep Fix::Rep_m1    = { 16, 1, 1, { 0x8000 } };
  47. Fix::Rep Fix::Rep_quotient_bump = { 16, 1, 1, { 0x4000 } };
  48.  
  49. // error handling
  50.  
  51. void
  52. Fix::default_error_handler(const char* msg)
  53. {
  54.   cerr << "Fix: " << msg << "\n";
  55.   abort();
  56. }
  57.  
  58. void
  59. Fix::default_range_error_handler(const char* msg)
  60. {
  61.   cerr << "Fix: range error in " << msg << "\n";
  62.   //abort();
  63. }
  64.  
  65. one_arg_error_handler_t 
  66.   Fix::error_handler = Fix::default_error_handler,
  67.   Fix::range_error_handler = Fix::default_range_error_handler;
  68.  
  69. one_arg_error_handler_t
  70. Fix::set_error_handler(one_arg_error_handler_t f)
  71. {
  72.   one_arg_error_handler_t old = error_handler;
  73.   error_handler = f;
  74.   return old;
  75. }
  76.  
  77. one_arg_error_handler_t
  78. Fix::set_range_error_handler(one_arg_error_handler_t f)
  79. {
  80.   one_arg_error_handler_t old = range_error_handler;
  81.   range_error_handler = f;
  82.   return old;
  83. }
  84.  
  85. void
  86. Fix::error(const char* msg)
  87. {
  88.   error_handler(msg);
  89. }
  90.  
  91. void
  92. Fix::range_error(const char* msg)
  93. {
  94.   range_error_handler(msg);
  95. }
  96.  
  97. // Fix::Rep allocation and initialization functions
  98.  
  99. static inline Fix::Rep*
  100. _new_Fix(_G_uint16_t len)
  101. {
  102.   int siz = (((_G_uint32_t) len + 15) >> 4);
  103.   if (siz <= 0) siz = 1;
  104.   unsigned int allocsiz = (sizeof(Fix::Rep) + (siz - 1) * sizeof(_G_uint16_t));
  105.   Fix::Rep* z = (Fix::Rep*)(new char[allocsiz]);
  106.   memset(z, 0, allocsiz);
  107.   z->len = len;
  108.   z->siz = siz;
  109.   z->ref = 1;
  110.   return z;
  111. }
  112.  
  113. Fix::Rep*
  114. Fix::new_Fix(_G_uint16_t len)
  115. {
  116.   return _new_Fix(len);
  117. }
  118.  
  119. Fix::Rep*
  120. Fix::new_Fix(_G_uint16_t len, const Rep* x)
  121. {
  122.   Rep* z = _new_Fix(len);
  123.   return copy(x,z);
  124. }
  125.  
  126. Fix::Rep*
  127. Fix::new_Fix(_G_uint16_t len, double d)
  128. {
  129.   Rep* z = _new_Fix(len);
  130.  
  131.   if ( d == max_value )
  132.   {
  133.     z->s[0] = 0x7fff;
  134.     for ( int i=1; i < z->siz; i++ )
  135.       z->s[i] = 0xffff;
  136.   }
  137.   else if ( d < min_value || d > max_value )
  138.     range_error("declaration");
  139.   else
  140.   {
  141.     if (d < 0)
  142.       d += 2.0;
  143.     d *= 32768;
  144.     for ( int i=0; i < z->siz; i++ )
  145.     {
  146.       z->s[i] = (_G_uint16_t )d;
  147.       d -= z->s[i];
  148.       d *= 65536;
  149.     }
  150.     if ( d >= 32768 )
  151.       z->s[z->siz-1]++;
  152.   }
  153.   mask(z);
  154.   return z;
  155. }
  156.  
  157. // convert to a double 
  158.  
  159. double
  160. value(const Fix& x)
  161. { 
  162.   double d = 0.0;
  163.   for ( int i=x.rep->siz-1; i >= 0; i-- )
  164.   {
  165.     d += x.rep->s[i];
  166.     d *= 1./65536.;
  167.   }
  168.   d *= 2.;
  169.   return d < 1. ? d : d - 2.;
  170. }
  171.  
  172. // extract mantissa to Integer
  173.  
  174. Integer
  175. mantissa(const Fix& x)
  176. {
  177.   Integer a = 1, b=1;
  178.   for ( int i=0; i < x.rep->siz; i++ )
  179.   {
  180.     a <<= 16;
  181.     a += x.rep->s[i];
  182.     b <<= 16;
  183.   }
  184.   return a-b;
  185. }
  186.  
  187. // comparison functions
  188.   
  189. inline static int
  190. docmp(const _G_uint16_t* x, const _G_uint16_t* y, int siz)
  191. {
  192.   int diff = (_G_int16_t )*x - (_G_int16_t )*y;
  193.   while ( --siz && !diff )
  194.     diff = (_G_int32_t )(_G_uint32_t )*++x - (_G_int32_t )(_G_uint32_t )*++y;
  195.   return diff;
  196. }
  197.  
  198. inline static int
  199. docmpz(const _G_uint16_t* x, int siz)
  200. {
  201.   while ( siz-- )
  202.     if ( *x++ ) return 1;
  203.   return 0;
  204. }
  205.  
  206. int
  207. Fix::compare(const Rep* x, const Rep* y)
  208. {
  209.   if ( x->siz == y->siz )
  210.     return docmp(x->s, y->s, x->siz);
  211.   else
  212.   {
  213.     int r;
  214.     const Rep* longer, *shorter;
  215.     if ( x->siz > y->siz )
  216.     {
  217.       longer = x;
  218.       shorter = y;
  219.       r = 1;
  220.     }
  221.     else
  222.     {
  223.       longer = y;
  224.       shorter = x;
  225.       r = -1;
  226.     }
  227.     int diff = docmp(x->s, y->s, shorter->siz);
  228.     if ( diff )
  229.       return diff;
  230.     else if ( docmpz(&longer->s[shorter->siz], longer->siz-shorter->siz) )
  231.       return r;
  232.     else
  233.       return 0;
  234.   }
  235. }
  236.  
  237. // arithmetic functions
  238.  
  239. Fix::Rep*
  240. Fix::add(const Rep* x, const Rep* y, Rep* r)
  241. {
  242.   _G_uint16_t xsign = x->s[0], ysign = y->s[0];
  243.   const Rep* longer, *shorter;
  244.   if ( x->len >= y->len )
  245.     longer = x, shorter = y;
  246.   else
  247.     longer = y, shorter = x;
  248.   if ( r == NULL )
  249.     r = new_Fix(longer->len);
  250.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  251.     r->s[i] = 0;
  252.   for ( ; i >= shorter->siz; i-- )
  253.     r->s[i] = longer->s[i];
  254.   _G_uint32_t sum = 0, carry = 0;
  255.   for ( ; i >= 0; i-- )
  256.   {
  257.     sum = carry + (_G_uint32_t )x->s[i] + (_G_uint32_t )y->s[i];
  258.     carry = sum >> 16;
  259.     r->s[i] = sum;
  260.   }
  261.   if ( (xsign ^ sum) & (ysign ^ sum) & 0x8000 )
  262.     overflow_handler(r);
  263.   return r;
  264. }
  265.  
  266. Fix::Rep*
  267. Fix::subtract(const Rep* x, const Rep* y, Rep* r)
  268. {
  269.   _G_uint16_t xsign = x->s[0], ysign = y->s[0];
  270.   const Rep* longer, *shorter;
  271.   if ( x->len >= y->len )
  272.     longer = x, shorter = y;
  273.   else
  274.     longer = y, shorter = x;
  275.   if ( r == NULL )
  276.     r = new_Fix(longer->len);
  277.   for ( int i=r->siz-1; i >= longer->siz; i-- )
  278.     r->s[i] = 0;
  279.   for ( ; i >= shorter->siz; i-- )
  280.     r->s[i] = (longer == x ? x->s[i] : -y->s[i]);
  281.   _G_int16_t carry = 0;
  282.   _G_uint32_t sum = 0;
  283.   for ( ; i >= 0; i-- )
  284.   {
  285.     sum = (_G_int32_t )carry + (_G_uint32_t )x->s[i] - (_G_uint32_t )y->s[i];
  286.     carry = sum >> 16;
  287.     r->s[i] = sum;
  288.   }
  289.   if ( (xsign ^ sum) & (~ysign ^ sum) & 0x8000 )
  290.     overflow_handler(r);
  291.   return r;
  292. }
  293.  
  294. Fix::Rep*
  295. Fix::multiply(const Rep* x, const Rep* y, Rep* r)
  296. {
  297.   if ( r == NULL )
  298.     r = new_Fix(x->len + y->len);
  299.   int xsign = x->s[0] & 0x8000,
  300.     ysign = y->s[0] & 0x8000;
  301.   Fix X(x->len), Y(y->len);
  302.   if ( xsign )
  303.     x = negate(x,X.rep);
  304.   if ( ysign )
  305.     y = negate(y,Y.rep);
  306.   for ( int i=0; i < r->siz; i++ )
  307.     r->s[i] = 0;
  308.   for ( i=x->siz-1; i >= 0; i-- )
  309.   {
  310.     _G_uint32_t carry = 0;
  311.     for ( int j=y->siz-1; j >= 0; j-- ) 
  312.     {
  313.       int k = i + j + 1;
  314.       _G_uint32_t a = (_G_uint32_t )x->s[i] * (_G_uint32_t )y->s[j];
  315.       _G_uint32_t b = ((a << 1) & 0xffff) + carry;
  316.       if ( k < r->siz )
  317.       {
  318.     b += r->s[k];
  319.         r->s[k] = b;
  320.       }
  321.       if ( k < (int)r->siz + 1 )
  322.         carry = (a >> 15) + (b >> 16);
  323.     }
  324.     r->s[i] = carry;
  325.   }
  326.   if ( xsign != ysign )
  327.     negate(r,r);
  328.   return r;
  329. }
  330.  
  331. Fix::Rep*
  332. Fix::multiply(const Rep* x, int y, Rep* r)
  333. {
  334.   if ( y != (_G_int16_t )y )
  335.     range_error("multiply by int -- int too large");
  336.   if ( r == NULL )
  337.     r = new_Fix(x->len);
  338.   for ( int i=r->siz-1; i >= x->siz; i-- )
  339.     r->s[i] = 0;
  340.   _G_int32_t a, carry = 0;
  341.   for ( ; i > 0; i-- )
  342.   {
  343.     a = (_G_int32_t) (_G_uint32_t )x->s[i] * y + carry;
  344.     r->s[i] = a;
  345.     carry = a >> 16;        // assumes arithmetic right shift
  346.   }
  347.   a = (_G_int32_t) (_G_int16_t )x->s[0] * y + carry;
  348.   r->s[0] = a;
  349.   a &= 0xffff8000L;
  350.   if ( a != (_G_int32_t)0xffff8000L && a != (_G_int32_t)0L ) {
  351.     r->s[0] = 0x8000 ^ x->s[0] ^ y;
  352.     overflow_handler(r);
  353.   }
  354.   return r;
  355. }
  356.  
  357. Fix::Rep*
  358. Fix::divide(const Rep* x, const Rep* y, Rep* q, Rep* r)
  359. {
  360.   int xsign = x->s[0] & 0x8000, 
  361.     ysign = y->s[0] & 0x8000;
  362.   if ( q == NULL )
  363.     q = new_Fix(x->len);
  364.   copy(&Rep_0,q);
  365.   if ( r == NULL )
  366.     r = new_Fix(x->len + y->len - 1);
  367.   if ( xsign )
  368.     negate(x,r);
  369.   else
  370.     copy(x,r);
  371.   Fix Y(y->len);
  372.   Rep* y2 = ( ysign ? negate(y,Y.rep) : copy(y,Y.rep) );
  373.   if ( !compare(y2) )
  374.     range_error("division -- division by zero");
  375.   else if ( compare(x,y2) >= 0 )
  376.     if ( compare(x,y2) == 0 && (xsign ^ ysign) != 0 )
  377.     {
  378.       copy(&Rep_m1,q);
  379.       copy(&Rep_0,r);
  380.     }
  381.     else
  382.       range_error("division");
  383.   else
  384.   {
  385.     Rep* t;
  386.     Fix S(r->len),
  387.       W(q->len,&Rep_quotient_bump);
  388.     for ( int i=1; i < q->len; i++ )
  389.     {
  390.       shift(y2,-1,y2);
  391.       subtract(r,y2,S.rep);
  392.       int s_status = compare(S.rep);
  393.       if ( s_status == 0 ) 
  394.       {
  395.     t = r, r = S.rep, S.rep = t;
  396.     break;
  397.       }
  398.       else if ( s_status > 0 )
  399.       {
  400.     t = r, r = S.rep, S.rep = t;
  401.     add(q,W.rep,q);
  402.       }
  403.       shift(W.rep,-1,W.rep);
  404.     }
  405.     if ( xsign ^ ysign )
  406.       negate(q,q);
  407.   }
  408.   return q;
  409. }
  410.  
  411. Fix::Rep*
  412. Fix::shift(const Rep* x, int y, Rep* r)
  413. {
  414.   if ( r == NULL )
  415.     r = new_Fix(x->len);
  416.   if ( y == 0 )
  417.     {
  418.       copy (x, r);
  419.       return r;
  420.     }
  421.  
  422.   int ay = abs((_G_int32_t) y),
  423.     ayh = ay >> 4,
  424.     ayl = ay & 0x0f;
  425.   int xl, u, ilow, ihigh;
  426.   _G_uint16_t *rs;
  427.   const _G_uint16_t *xsl, *xsr;
  428.  
  429.   if ( y > 0 )
  430.   {
  431.     rs = r->s;
  432.     xsl = x->s + ayh;
  433.     xsr = xsl + 1;
  434.     xl = ayl;
  435.     u = 1;
  436.     ihigh = x->siz - ayh - 1;
  437.     ilow = 0;
  438.   }
  439.   else
  440.   {
  441.     rs = &r->s[r->siz - 1];
  442.     xsr = &x->s[r->siz - 1] - ayh;
  443.     xsl = xsr - 1;
  444.     xl = 16 - ayl;
  445.     u = -1;
  446.     ihigh = r->siz - ayh - 1;
  447.     ilow = ihigh - x->siz;
  448.   }
  449.  
  450.   int xr = 16 - xl;
  451.   _G_uint16_t xrmask = 0xffffL >> xr;
  452.   for ( int i=0; i < ilow; i++, rs+=u, xsl+=u, xsr+=u )
  453.     *rs = 0;
  454.   for ( ; i < ihigh; i++, rs+=u, xsl+=u, xsr+=u )
  455.     *rs = (*xsl << xl) + ((*xsr >> xr) & xrmask);
  456.   *rs = (y > 0 ? (*xsl << xl) : ((*xsr >> xr) & xrmask));
  457.   rs += u;
  458.   for ( ; ++i < r->siz; rs+=u )
  459.     *rs = 0;
  460.   return r;
  461. }
  462.  
  463. Fix::Rep*
  464. Fix::negate(const Rep* x, Rep* r)
  465. {
  466.   if ( r == NULL )
  467.     r = new_Fix(x->len);
  468.   _G_uint32_t carry = 1;
  469.   for ( int i=r->siz-1; i >= x->siz; i-- )
  470.     r->s[i] = 0;
  471.   for ( ; i >= 0; i-- )
  472.   {
  473.     _G_uint32_t a = (_G_uint16_t )~x->s[i] + carry;    // bug work-around
  474.     r->s[i] = a;
  475.     carry = a >> 16;
  476.   }
  477.   return r;
  478. }
  479.  
  480. // io functions
  481.  
  482. Fix
  483. atoF(const char* a, int len)
  484. {
  485.   return Fix(len,atof(a));
  486. }
  487.  
  488. extern AllocRing _libgxx_fmtq;
  489.  
  490. void
  491. Fix::printon(ostream& s, int width) const
  492. {
  493.   double val = value(*this);
  494.   int old_precision = s.precision(width-3);
  495.   _G_int32_t old_flags = s.setf(ios::fixed, ios::fixed|ios::scientific);
  496.   if (val >= 0)
  497.       s << ' ';
  498.   s.width(width-2);
  499.   s << val;
  500.   s.precision(old_precision);
  501.   s.flags(old_flags);
  502. }
  503.  
  504. char*
  505. Ftoa(Fix& x, int width)
  506. {
  507.   int wrksiz = width + 2;
  508.   char *fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  509.   ostrstream stream(fmtbase, wrksiz);
  510.   
  511.   x.printon(stream, width);
  512.   stream << ends;
  513.   return fmtbase;
  514. }
  515.  
  516. extern Obstack _libgxx_io_ob;
  517.  
  518. Fix
  519. Fix::operator %= (int y)
  520. {
  521.   Fix r((int )rep->len + y, *this); return *this = r;
  522. }
  523.  
  524. istream&
  525. operator >> (istream& s, Fix& y)
  526. {
  527.   int got_one = 0;
  528.   if (!s.ipfx(0))
  529.   {
  530.     s.clear(ios::failbit|s.rdstate()); // Redundant if using GNU iostreams.
  531.     return s;
  532.   }
  533.  
  534.   char sign = 0, point = 0;
  535.   char ch;
  536.   s >> ws;
  537.   if (!s.good())
  538.   {
  539.     s.clear(ios::failbit|s.rdstate());
  540.     return s;
  541.   }
  542.   while (s.get(ch))
  543.   {
  544.     if (ch == '-')
  545.     {
  546.       if (sign == 0)
  547.       {
  548.         sign = 1;
  549.         _libgxx_io_ob.grow(ch);
  550.       }
  551.       else
  552.         break;
  553.     }
  554.     if (ch == '.')
  555.     {
  556.       if (point == 0)
  557.       {
  558.         point = 1;
  559.         _libgxx_io_ob.grow(ch);
  560.       }
  561.       else
  562.         break;
  563.     }
  564.     else if (ch >= '0' && ch <= '9')
  565.     {
  566.       got_one = 1;
  567.       _libgxx_io_ob.grow(ch);
  568.     }
  569.     else
  570.       break;
  571.   }
  572.   char * p = (char*)(_libgxx_io_ob.finish(0));
  573.   if (s.good())
  574.     s.putback(ch);
  575.   if (!got_one)
  576.     s.clear(ios::failbit|s.rdstate());
  577.   else
  578.     y = atoF(p);
  579.   _libgxx_io_ob.free(p);
  580.   return s;
  581. }
  582.  
  583. void
  584. show(const Fix& x)
  585. {
  586.   cout << "len = " << x.rep->len << "\n";
  587.   cout << "siz = " << x.rep->siz << "\n";
  588.   cout << "ref = " << x.rep->ref << "\n";
  589.   cout << "man = ";
  590. #ifdef _OLD_STREAMS
  591.   cout << Itoa(mantissa(x),16,4*x.rep->siz);
  592. #else
  593.   int old_flags = cout.setf(ios::hex, ios::hex|ios::dec|ios::oct);
  594.   cout.width(4*x.rep->siz);
  595.   cout << mantissa(x);
  596.   cout.setf(old_flags, ios::hex|ios::dec|ios::oct);
  597. #endif
  598.   cout << "\n";
  599.   cout << "val = " << value(x) << "\n";
  600. }
  601.  
  602. // parameter setting operations
  603.  
  604. Fix::PEH Fix::set_overflow_handler(PEH new_handler)
  605. {
  606.   PEH old_handler = overflow_handler;
  607.   overflow_handler = new_handler;
  608.   return old_handler;
  609. }
  610.  
  611. int
  612. Fix::set_default_length(int newlen)
  613. {
  614.   _G_uint16_t oldlen = default_length;
  615.   if ( newlen < min_length || newlen > max_length )
  616.     error("illegal length in Fix::set_default_length");
  617.   default_length = newlen;
  618.   return oldlen;
  619. }
  620.  
  621. // overflow handlers
  622.  
  623. void
  624. Fix::overflow_saturate(Rep* r)
  625. {
  626.   if ( (_G_int16_t) r->s[0] > 0 ) 
  627.   {
  628.     r->s[0] = 0x8000;
  629.     for ( int i=1; i < r->siz; i++ )
  630.       r->s[i] = 0;
  631.   }
  632.   else
  633.   {
  634.     r->s[0] = 0x7fff;
  635.     for ( int i = 1; i < (int)r->siz; i++ )
  636.       r->s[i] = 0xffff;
  637.     mask(r);
  638.   }
  639. }
  640.  
  641. void
  642. Fix::overflow_wrap(Rep*)
  643. {}
  644.  
  645. void
  646. Fix::overflow_warning_saturate(Rep* r)
  647. {
  648.   overflow_warning(r);
  649.   overflow_saturate(r);
  650. }
  651.  
  652. void
  653. Fix::overflow_warning(Rep*)
  654. {
  655.   cerr << "Fix: overflow warning\n"; 
  656. }
  657.  
  658. void
  659. Fix::overflow_error(Rep*)
  660. {
  661.   cerr << "Fix: overflow error\n"; 
  662.   abort();
  663. }
  664.